package com.fallsvc.re.javasesets.sort;

import java.util.Arrays;
import java.util.Stack;

/**
 * @auther falls_vc
 * description:
 * @date 2025/10/21  9:53
 */
public class Demo1 {


    // 插入排序
    public static void insertSort(Integer[] array) {

        for (int i = 1; i < array.length; i++) {
            Integer tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j -= 1) {
                if(array[j]>tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    // 希尔排序
    public static void shellSort(Integer[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }

    private static void shell(Integer[] array, int gap) {

        for (int i = gap; i < array.length; i += gap) {
            Integer tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if(array[j]>tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    // 选择排序
    public static void selectSort(Integer[] array) {
        for (int i = 1; i < array.length; i++) {
            int minIndex = i - 1;
            for (int j = i; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i-1);
        }
    }

    private static void swap(Integer[] array, int x, int y) {
        Integer tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
    // 双向选择
    public static void selectSortTwo(Integer[] array) {
        int left = 0;
        int right = array.length-1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = right;
            for (int i = left;i <= right;i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            // 是否最大值下标的元素已被交换
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);

            left++;
            right--;
        }
    }
    // 创建堆
    public static void createHeap(Integer[] array) {
        int end = (array.length - 2) / 2;
        while(end >= 0) {
            shiftDown(array,end,array.length);
            end--;
        }
    }
    // 向下调整
    public static void shiftDown(Integer[] array,int cur,int size) {
        int parent = cur;
        int child = cur * 2 + 1;
        while (child < size) {
            if(child + 1 < size && array[child+1] < array[child]) {
                child++;
            }
            if(array[parent] > array[child]) {
                swap(array,parent,child);
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }

    // 堆排
    public static void heapSort(Integer[] array) {
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            shiftDown(array,0, end );
            end--;
        }
    }
    // 冒泡排序
    public static void bubbleSort(Integer[] array) {

        for (int i = 0; i < array.length-1; i++) { // -1 优化1少排一次
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if (!flag) { // 没有交换
                break;
            }
        }
    }

    public static void quickSort(Integer[] array) {
//        quick(array,0,array.length-1);

        quickSortNonR(array,0,array.length-1);
    }

    // 非递归
    public static void quickSortNonR(Integer[] a, int left, int right) {
        Stack<Integer> st = new Stack<>();
        st.push(left);
        st.push(right);
        while (!st.empty()) {
            right = st.pop();
            left = st.pop();
            if(right - left <= 1)
                continue;
            int div = partition(a, left, right);
// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
            st.push(div+1);
            st.push(right);
            st.push(left);
            st.push(div-1);
        }
    }
    private static void quick(Integer[] array, int start, int end) {
        if(start >= end) return;
        // 元素少于10 直接插入排序
        if(end-start+1<=10){
            insertSortRange(array,start,end);
            return;
        }
        // 1.找中间数下标 三数取中
        int middleIndex = getMiddleIndex(array,start,end);
        swap(array,start,middleIndex);
        // 2.排序返回中间值下标
        int pivot = partition(array,start,end);
        if (pivot == -1) return;
        // 3.递归
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private static void insertSortRange(Integer[] array, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    // 挖坑法
    private static int partition(Integer[] array, int start, int end) {
        int tmp = array[start];
        while(start < end) {
            while(start < end && array[end] >= tmp) end--;
            array[start] = array[end];
            while(start < end && array[start] <= tmp) start++;
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    public static void main2(String[] args) {
        Integer[] a = {3,1,2,4,5};
        partition(a,0,4);
        System.out.println(Arrays.toString(a));
    }

    private static int getMiddleIndex(Integer[] array, int start, int end) {
        int mid = (end - start)/2 + start;
        return array[start] > array[mid]
                ? (array[start] < array[end] ? start : array[mid] > array[end] ? mid : end)
                : (array[start] < array[end] ? array[mid] > array[end] ? end : mid : start);

    }

    public static void main1(String[] args) {
        Integer[] a = {1,3,2,1};
        System.out.println(getMiddleIndex(a, 0, 2));
    }

    // 归并排序
    public static void mergeSort(Integer[] array) {
        mergeSortTmp(array,0,array.length-1);

    }

    private static void mergeSortTmp(Integer[] array, int start, int end) {
        if(start >= end) return;
        int mid = (start+end) / 2;

        mergeSortTmp(array,start,mid);
        mergeSortTmp(array,mid + 1,end);
        // 拆分的两个有序数组进行排序
        merge(array,start,mid,end);
    }

    private static void merge(Integer[] array, int start, int mid, int end) {

        int s1=start;
        int s2=mid+1;
        Integer[] count=new Integer[end-start+1];
        int k=0;
        //从小到大放入count数组
        while(s1<=mid&&s2<=end){
            if(array[s1]<=array[s2]){
                count[k++]=array[s1++];
            }else{
                count[k++]=array[s2++];
            }
        }

        while(s1<=mid){
            count[k++]=array[s1++];
        }
        while(s2<=end){
            count[k++]=array[s2++];
        }
        //放回原数组 k为数组元素个数
        s1=start;
        for (int i = 0; i < k; i++) {
            array[s1++]=count[i];
        }

        // 错误写了if 还检查半天没有发现
//        Integer[] tmp = new Integer[end-start+1];
//        int s1 = start;
//        int s2 = mid + 1;
//        int k = 0;
//        while(s1 <= mid && s2 <= end) {
//            if(array[s1] <= array[s2]) {
//                tmp[k++] = array[s1++];
//            }else {
//                tmp[k++] = array[s2++];
//            }
//        }
//        if(s1 <= mid) {
//            tmp[k++] = array[s1++];
//        }
//        if(s2 <= end) {
//            tmp[k++] = array[s2++];
//        }
//        // 有序放回去
//        s1 = start;
//        for (int i = 0; i < tmp.length; i++) {
//            array[s1++] = tmp[i];
//        }
    }

    public static void main(String[] args) {
//        int i =  1;
//        for (; i < 10; i++) {
//            if (i == 5) {
//                break;
//            }
//        }
//        System.out.println(i);
        Integer[] array = {9,8,7,3,4,1};
//        insertSort(array);
//        shellSort(array);
//        selectSort(array);
//        selectSortTwo(array);

//        createHeap(array);
//        heapSort(array);
//        bubbleSort(array);
//        quickSort(array);
        mergeSort(array);

        System.out.println(Arrays.toString(array));
    }
}
